package java学习.代码随想录.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/30 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 打家劫舍II {

    /**
     * 1. dp[i] 前i个房间的最大金额
     * 2. 环形房子：第一个和最后一个不能同时偷：
     *     (1) 偷第一个。
     *     (2) 偷最后一个
     *     (3) 都不偷
     */
    public static  int rob(int[] nums){
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        int []num1 =  nums.clone();
        num1[0] = 0;
        int []num2 =  nums.clone();
        num2[nums.length-1] = 0;

        int []num3 =  nums.clone();
        num3[0] = 0;
        num3[nums.length-1] = 0;

        int result = Math.max(func(num1),func(num2));
        return Math.max(result,func(num3));
    }
    public static int func(int[] nums){
        int []dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);
        for (int i = 2; i < dp.length; i++) {

            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[dp.length-1];
    }

    public static  int rob2(int[] nums){
    int n = nums.length;
    if (n== 0)
        return 0;
    if (n == 1)
        return nums[0];
    if (n==2){
        return Math.max(nums[0],nums[1]);
    }
    int result = Math.max(funcThreeVariable(nums,0,n-2),funcThreeVariable(nums,1,n-2));
    return  Math.max(result,funcThreeVariable(nums,1,n-1));
}

    public static int funcThreeVariable(int[] nums,int start,int end ){
        // 开偷第一家
        int a = nums[start];
        //        开偷第二家
        int b = Math.max(nums[start],nums[start+1]);
        for (int i = start+2; i <=end; i++) {
            int c = b;
            b = Math.max(a+nums[i],b);
            a = c;
        }
        return b;
    }
        public static int rob3(int[] nums) {
            if (nums.length == 1)return nums[0];
            if (nums.length == 2)return Math.max(nums[0],nums[1]);
            //进行区间选取  是不是很简单~
            return Math.max(
                    method(Arrays.copyOfRange(nums,0,nums.length-1)),
                    method(Arrays.copyOfRange(nums,1,nums.length)));
        }
        //这个就是打家劫舍Ⅰ

    public static int method(int []nums){
            int []dp = new int [nums.length+1];
            dp[0] = 0;
            dp[1] = nums[0];
            for (int i = 2;i< nums.length+1;i++){
                dp[i] = Math.max(nums[i-1]+dp[i-2],dp[i-1]);
            }
            return dp[nums.length] ;
    }
    public static void main(String[] args) {
        int[] n = {2,3,2};
        int[] n1 = {1,2,3,1};
        int[] n2 = {1,7,9,2};
        System.out.println(rob2(n2));
        System.out.println("---------");
        System.out.println(rob3(n2));
//        String a=null;
//        if("aa".equals(a))//这种情形，不出现空指针异常
//        //if(a.equals("aa"))//出现空指针异常
//        {
//            System.out.println(true);
//        }
//        else {
//            System.out.println(false);
//        }
    }

    public static int funcX(int[] nums,int start,int end ){
        int []dp = new int[nums.length];
        // 开偷第一家
        dp[0] = nums[start];
//        开偷第二家
        dp[1] = Math.max(dp[0],nums[start+1]);
        for (int i = start+2; i <=end; i++) {

            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
}
